/**
 * @a https://leetcode.cn/problems/word-ladder/
 */

#include "../../common.h"


class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(beginWord == endWord) return 1;
        unordered_set<string> wordbank(wordList.begin(),wordList.end());
        if(!wordbank.count(endWord)) return 0;
        unordered_set<string> visited;

        queue<string> que;
        que.push(beginWord);
        visited.insert(beginWord);
        int cnt = 1;
        while(que.size()){
            int sz = que.size();
            ++cnt;
            while(sz--){
                string cur_str = que.front();
                que.pop();
                for(int i = 0; i < cur_str.size(); ++i){
                    string tmp = cur_str;
                    for(char j = 'a'; j <= 'z'; ++j){
                        tmp[i] = j;
                        if(wordbank.count(tmp) && !visited.count(tmp)){
                            if(tmp == endWord) return cnt;
                            que.push(tmp);
                            visited.insert(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};